﻿/* 13. *** Write a program that sorts an array of integers using the merge sort algorithm. */

using System;
using System.Collections.Generic;

public class MergeSortAlgorithm
{
    public static List<double> array = new List<double>();

    public static void Main()
    {
        DataInput();

        Console.WriteLine("\nArray :");
        PrintArray(array);

        array = MergeSort(array);

        Console.WriteLine("Sorted array :");
        PrintArray(array);
    }

    public static void DataInput()
    {
        int arrayLength;

        do
        {
            Console.Clear();
            Console.Write("\nThe length of array: ");
            if (int.TryParse(Console.ReadLine(), out arrayLength) && (0 < arrayLength))
                break;
        } while (true);

        Console.WriteLine();
        for (int i = 0; i < arrayLength; i++)
        {
            Console.Write("Array[{0}] = ", i);
            array.Add(double.Parse(Console.ReadLine()));
        }
    }

    public static void PrintArray(List<double> array)
    {
        Console.Write("{0}", array[0]);
        for (int i = 1; i < array.Count; i++)
            Console.Write(", {0}", array[i]);

        Console.WriteLine("\n");
    }

    public static List<double> MergeSort(List<double> array)
    {
        int left;
        int right;
        int middle = array.Count / 2;
        List<double> leftArray = array.GetRange(0, middle);
        List<double> rightArray = array.GetRange(middle, array.Count - middle);
        List<double> sorted = new List<double>();

        if (array.Count == 1)
            return array;

        leftArray = MergeSort(leftArray);
        rightArray = MergeSort(rightArray);

        left = 0;
        right = 0;

        for (int i = 0; i < leftArray.Count + rightArray.Count; i++)
            if (left == leftArray.Count)
                sorted.Add(rightArray[right++]);
            else if (right == rightArray.Count)
                sorted.Add(leftArray[left++]);
            else if (leftArray[left] < rightArray[right])
                sorted.Add(leftArray[left++]);
            else
                sorted.Add(rightArray[right++]);

        return sorted;
    }
}